You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

給定兩個整數陣列nums1和nums2，兩陣列皆以升冪排列。除此之外，另外給定兩個整數m、 n，分別代表兩陣列nums1、nums2中元素的數量。
請將陣列nums1、nums2合併成單一陣列並且以升冪排列。

最後合併好的有序陣列不須特別回傳，而是需要儲存在陣列nums1中。為了滿足這個條件，陣列nums1會有長度m+n，m代表了陣列nums1中有m個需要被合併的元素數量，n則代表了陣列nums1中扣除m後剩餘的元素數量，這n個元素都被設定為0。陣列nums2的長度為n。

閱讀完題目，其實就是兩個陣列比大小，比完之後由小至大排列，但只能排列在陣列nums1中。

徒手上陣 - Bubble Sort
第一次徒手上陣寫這題時，想法很簡單，先把nums2裡面的整數，取代nums1中整數為0的位置，放進去nums1後，再使用氣泡排序法(Bubble Sort)的方式進行由小至大的排序。
程式碼如下 :

var merge = function(nums1, m, nums2, n) {
  let j = 0
  for (let i = m; i < (m + n); i++) {
    nums1[i] = nums2[j]
    j++
  }
  for (let i = 0; i < nums1.length - 1; i++){
     for (let k = i+1; k < nums1.length; k++){
      if (nums1[i] > nums1[k]) {
        let tempValue = nums1[i]
        nums1[i] = nums1[k]
        nums1[k] = tempValue
      }
    }   
  }
  return nums1
};

磨刀上陣 - K-Way Merge
改使用K-Way Merge解題，一開始的想法是 兩個陣列從index 0的位置開始比較大小，想到這邊就卡住了，因為題目規定要回傳nums1且必須原地(in-place)修改nums1，所以這招行不通

既然正著不能做，那就反著做

1. 從陣列nums1的 m-1位置 跟 陣列nums2的 n-1位置 開始比較、進行降冪排列，所以要從最大數開始排列，只要整數較大就放進nums1的pointer3位置，而pointer3毫無疑問的，會從陣列nums1的尾端開始向index 0的位置移動
2. pointer1跟pointer2分別代表了nums1的m-1位置 以及 nums2的n-1位置

var merge = function(nums1, m, nums2, n) {
  let pointer1 = m - 1;// for nums1
  let pointer2 = n - 1;// for nums2
  let pointer3 = m + n - 1;
  let mergedArr = [];
  while(pointer2 >= 0 ){
    if (nums1[pointer1] > nums2[pointer2]){ //表示nums1還沒檢查完
        nums1[pointer3] = nums1[pointer1];
        pointer1--;
    }else {
        nums1[pointer3] = nums2[pointer2];
        pointer2--;
    }
    pointer3--;
  }
};

其實一開始我以為這題是要練習氣泡排序法(Bubble Sort)，不過看起來K-Way Merge對於時間複雜度更具優勢
時間複雜度從O(n)→O(n log K)

看來該好好練習K-Way Merge了!今天就先到這吧! 晚安各位!